package com.cty._06_TwoExamples._68_CommonParentInTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: cty
 * @Date: 2020/7/26 18:15
 * @Description: 面试题68（二）：树中的两个节点的最低公共祖先
 * @version: 1.0
 */
public class CommonParentInTree {

    public static TreeNode commonParentInTree(TreeNode treeRoot, TreeNode A, TreeNode B){
        if(treeRoot==null || A==null || B==null)
            return null;

        // 两个链表求第一个相同节点
        List<TreeNode> pathA = new ArrayList<>();
        List<TreeNode> pathB = new ArrayList<>();
        if(getPathToCommonParent(treeRoot, A, pathA) && getPathToCommonParent(treeRoot, B, pathB)){
            List<TreeNode> shortPath = pathA.size()<pathB.size()?pathA:pathB;
            List<TreeNode> longPath = pathA.size()>=pathB.size()?pathA:pathB;
            int diffLen = longPath.size() - shortPath.size();

            for(int i=0; i<shortPath.size(); i++){
                if(longPath.get(diffLen+i).value == shortPath.get(i).value)
                    return shortPath.get(i);
            }  // end for
        }  // end if
        return null;
    }  // end commonParentInTree()

    // 后序遍历获取路径
    private static boolean getPathToCommonParent(TreeNode treeRoot, TreeNode node, List<TreeNode> list){
        if(treeRoot.value == node.value) {
            list.add(treeRoot);
            return true;
        }

        boolean found = false;
        for(int i=0; !found && i<treeRoot.children.size(); i++)
            found = getPathToCommonParent(treeRoot.children.get(i), node, list);

        if(found)
            list.add(treeRoot);
        return found;
    }  // end getPathToCommonParent()

}  // end class

class TreeNode {
    int value;
    List<TreeNode> children;

    public TreeNode(){children = new ArrayList<>();}
    public TreeNode(int value){this.value = value; children = new ArrayList<>();}
}  // end class


